Learning Python3 C1

[TOC]

Before Math

Assuming all the compile should be involved in int32 type, which means every returned answer should be limited in [-2^31, 2^31-1]

There’s only two basic calculations : Addition and Subtraction , and three basic bool judgments : ‘More than’ , ‘Less than’ and ‘Equal’, which composed all algorithm next.

Integer: Basic Attributes

I personally regard the symbol and the value as two divided attributes in a single integer. Thus, to use if(int<0) to check whether the integer is negative is quite useful, we can quickly multiply -1 to it , and use another variable to save its symbol. It’s useful when the problem do not care symbol, for example, Problem 7: Reverse Integer.

We can simply isolate the symbol, do reverse operation in whatever way you like , and reduce symbol:

class Solution:
    def reverse(self, x: int) -> int:
        if x<0:#check negativity
            x=-x
            flag=-1
        else:
            flag=1
        s = str(x)
        s=s[::-1]
        res = int(s)*flag #convert to string and reverse
        if res < -2**31 or res>2**31-1: #check overflow
            return 0
        else:
            return res

However, everything above can be represented as 3 lines with totally same thought of solution:

    s = cmp(x, 0)#check negativity
    r = int(`s*x`[::-1])#convert to string and reverse
    return s*r * (r < 2**31)#check overflow
#By StefanPochmann

Integer: Get Each Number

Some times we need to get each number of a integer, for example (int)1234, we hope we can get 1, 2,3,4 each time, or 4,3,2,1 each time. Next I use Problem 2 : Add Two Numbers as an example.

Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

First we talk about having the sum 807, How do we get each number of this sum and put it in each node of final linked list?

We can use such scheme: 123% 10 = 3, 123-3 % 100 = 20 , 123 -20 -3 %1000 = 100 . And 3 /1 =3 , 20/10 = 2 , 100/100 = 1. This law can be used in every integer.

Next, How we assemble a integer by getting single digit each time? The answer is quite easy: 3x1=3, 2x10=20,1x100=100. 3+20+100 = 123.

Thus the solution is clear:

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        N=0
        N1=0
        N2=0
        while(l1!=None):#get each digit of l1
            N1=N1+l1.val*pow(10,N)
            l1=l1.next
            N=N+1
        N=0
        while(l2!=None):#get each digit of l2
            N2=N2+l2.val*pow(10,N)
            l2=l2.next
            N=N+1
        Sum=N1+N2 #get plused result
        length=len(str(Sum))#check number of digits to create nodes
        nodes=[]
        i=1
        while(i<=length):
            node=ListNode(int((Sum % pow(10,i))/pow(10,i-1)))#get each digit number of result
            nodes.append(node)
            i=i+1
        for i in range(0,length-1):
            nodes[i].next=nodes[i+1]
        return nodes[0]

However, we can plus each list’s unit's digit , ten's digit together at the same time , and put every result in single variable. Moreover, use same loop to put each digit in result linked list , and use divmod to get each number.

def addTwoNumbers(self, l1, l2):
        carry = 0
        res = n = ListNode(0)
        while l1 or l2 or carry:#while carry :check number of digits to create nodes
            if l1:
                carry += l1.val#get each digit of l1 and plus
                l1 = l1.next
            if l2:
                carry += l2.val;#get each digit of l2 and plus
                l2 = l2.next
            carry, val = divmod(carry, 10)#get each digit number of result
            n.next = n = ListNode(val)
        return res.next

Another approach to get each digit is to use n%10

For example:


while(n>0):
	print(n%10)
	n/=10

Integer: Division From Basic

Describpion

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.

Example

Input: dividend = 10, divisor = 3
Output: 3

At first we all can think of setting a counter, and make subtraction each time like :

counter = 0
WHILE dividend > 0
    dividend -= divisor
    counter++
return counter

However, this would be O(n) , which is too slow. We can try to set the ‘divisor’ as large as possible by multiply 2 until it can’t be larger, and then make the subtraction. This will be O(logn):

div = divisor //save the divisor
res=0
WHILE dividend > 0
	counter = 1
	WHILE div < dividend
		div<<=1 //<<= is faster than div = div*2
		counter<<=1
	dividend -= div
	res += counter
return res

In Python with overflow control:

res=0
        if ((dividend<0) is (divisor<0)) == False:
            flag=-1
        else:
            flag=1
        if dividend==0:
            return 0
        if dividend==-2147483648 and divisor==-1:
            return 2**31-1
        dividend=abs(dividend)
        divisor=abs(divisor)
        while dividend-divisor>=0:
            temp=divisor
            counter=1
            while dividend>=temp*2:
                temp=temp*2
                counter=counter*2
            dividend=dividend-temp
            res+=counter
        res=res*flag
        if res<-2**31 or res>2**31-1:
            return 2**31-1
        else:
            return res

Clear vision by lee215:

sig = (a < 0) == (b < 0)
        a, b, res = abs(a), abs(b), 0
        while a >= b:
            x = 0
            while a >= b << (x + 1): x += 1
            res += 1 << x
            a -= b << x
        return min(res if sig else -res, 2147483647)